﻿#ifndef __SS_HASHMAP_H__
#define __SS_HASHMAP_H__
#include "../algorithms/ssHash.h"
#include "ssPair.h"
#include "ssNumArray.h"
#include "ssList.h"
#include "../string/ssString.h"


namespace StarSeeker
{
	template<typename K,typename V>
	class ssHashmap
	{
	public:
		ssHashmap(ulint maxCount=16);//必须为2的n次幂
		ssHashmap(const ssHashmap& hm);
		~ssHashmap();
		void operator= (const ssHashmap& hm);
		//查找元素
		V* Find(const K& k);
		//插入
		bool Insert(const K& k, V& val);
		bool InsertCover(const K& k, V& val);
		//删除
		bool Remove(const K& k);
		//释放内存
		void Clear();
	private:
		//计算哈希值
		ulint GetHash(const ulint& k);
		ulint GetHash(const ssString& k);
		//哈希值转数组索引
		ulint GetIndex(ulint hash);
		//从另一个容器复制过来
		void CopyFrom(const ssHashmap& hm);
		//扩容
		void Expanded();
	private:
		ssNumArray<ssList<ssPair<ulint,V> >*>	m_arr;
		ulint									m_maxCount;//必须为2的n次幂，扩容成2倍扩大，扩容后旧数组的索引对应新数组不变
		ulint									m_count;//元数总个数
	};

	template<typename K, typename V>
	inline ssHashmap<K, V>::ssHashmap(ulint maxCount)
	{
		if (maxCount==0 || (maxCount&maxCount-1) != 0)
		{
			SS_THROW("The number must be n-th power of 2")
		}
		m_arr.Init(maxCount);
		m_maxCount = maxCount;
		m_count = 0;
	}

	template<typename K, typename V>
	inline ssHashmap<K, V>::ssHashmap(const ssHashmap & hm)
	{
		CopyFrom(hm);
	}

	template<typename K, typename V>
	inline ssHashmap<K, V>::~ssHashmap()
	{
		Clear();
	}

	template<typename K, typename V>
	inline void ssHashmap<K, V>::operator=(const ssHashmap & hm)
	{
		CopyFrom(hm);
	}

	template<typename K, typename V>
	inline V * ssHashmap<K, V>::Find(const K& k)
	{
		ulint hash = GetHash(k);
		ulint index = GetIndex(hash);
		if (m_arr[index])
		{
			for (typename ssList<ssPair<ulint, V> >::Iterator itr = m_arr[index]->Begin(); itr!= m_arr[index]->End(); ++itr)
			{
				if (itr.Data() && itr.Data()->first == hash)
				{
					return &itr.Data()->second;
				}
			}
		}
		return 0;
	}

	template<typename K, typename V>
	inline bool ssHashmap<K, V>::Insert(const K& k, V & val)
	{
		ulint hash = GetHash(k);
		ulint index = GetIndex(hash);
		if (m_arr[index])
		{
			typename ssList<ssPair<ulint, V> >::Iterator itr = m_arr[index]->Begin();
			while (itr.IsVaild())
			{
				if (itr.Data()==0 || itr.Data()->first==hash)
				{
					return false;
				}
				++itr;
			}
			m_arr[index]->PushBack(ssPair<ulint, V>(hash, val));
			m_count++;
			return true;
		}
		else
		{
			m_arr[index] = new ssList<ssPair<ulint, V> >;
			m_arr[index]->PushBack(ssPair<ulint, V>(hash, val));
			m_arr.SetCount(m_arr.Count() + 1);
			m_count++;
			Expanded();
			return true;
		}
	}

	template<typename K, typename V>
	inline bool ssHashmap<K, V>::InsertCover(const K& k, V & val)
	{
		ulint hash = GetHash(k);
		ulint index = GetIndex(hash);
		if (m_arr[index])
		{
			typename ssList<ssPair<ulint, V> >::Iterator itr = m_arr[index]->Begin();
			while (itr.IsVaild())
			{
				if (itr.Data() && itr.Data()->first == hash)
				{
					itr.Data()->second = val;
					return true;
				}
				++itr;
			}
			m_arr[index]->PushBack(ssPair<ulint, V>(hash, val));
			m_count++;
			return true;
		}
		else
		{
			m_arr[index] = new ssList<ssPair<ulint, V> >;
			m_arr[index]->PushBack(ssPair<ulint, V>(hash, val));
			m_arr.SetCount(m_arr.Count() + 1);
			m_count++;
			Expanded();
			return true;
		}
	}

	template<typename K, typename V>
	inline bool ssHashmap<K, V>::Remove(const K & k)
	{
		ulint hash = GetHash(k);
		ulint index = GetIndex(hash);
		if (m_arr[index])
		{
			for (typename ssList<ssPair<ulint, V> >::Iterator itr = m_arr[index]->Begin(); itr != m_arr[index]->End(); ++itr)
			{
				if (itr.Data() && itr.Data()->first == hash)
				{
					m_arr[index]->EraseItr(itr);
					if (m_arr[index]->Size()==0)
					{
						delete m_arr[index];
						m_arr[index] = 0;
						m_arr.SetCount(m_arr.Count() - 1);
					}
					m_count--;
					return true;
				}
			}
		}
		return false;
	}

	template<typename K, typename V>
	inline void ssHashmap<K, V>::Clear()
	{
		for (ulint i = 0; i < m_arr.MaxCount(); i++)
		{
			if (m_arr[i])
			{
				delete m_arr[i];
				m_arr[i] = 0;
			}
		}
		m_arr.SetCount(0);
		m_maxCount = 0;
		m_count = 0;
	}

	template<typename K, typename V>
	inline ulint ssHashmap<K, V>::GetHash(const ulint & k)
	{
		return k;
	}

	template<typename K, typename V>
	inline ulint ssHashmap<K, V>::GetHash(const ssString & k)
	{
		return DJBHashCode<char>(k.GetString(), k.Length());
	}

	template<typename K, typename V>
	inline ulint ssHashmap<K, V>::GetIndex(ulint hash)
	{
		return hash&(m_maxCount-1);
	}

	template<typename K, typename V>
	inline void ssHashmap<K, V>::CopyFrom(const ssHashmap & hm)
	{
		Clear();
		m_arr.Resize(hm.m_arr.MaxCount());
		for (ulint i = 0; i < hm.m_arr.MaxCount(); i++)
		{
			if (hm.m_arr[i])
			{
				m_arr[i] = new ssList<ssPair<ulint, V> >;
				*m_arr[i] = *hm.m_arr[i];
			}
		}
		m_maxCount = hm.m_arrCount;
		m_count = hm.m_count;
	}

	template<typename K, typename V>
	inline void ssHashmap<K, V>::Expanded()
	{
		if (m_arr.Count() > m_maxCount*75/100)
		{
			m_maxCount *= 2;
			m_arr.Resize(m_maxCount);
		}
	}

}
#endif
